# Worst-Case Convergence Time of ML Algorithms via Extreme Value Theory

arXiv: https://arxiv.org/abs/2404.07170 · HTML: https://mlsanity.com/paper/2404.07170/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 45 references that are in the map.
- First posted on arXiv 10 Apr 2024.

## Builds on (most cited first, 6 of 6)

- [Green AI](https://mlsanity.com/paper/1907.10597/) (2019)
- [Detecting and Understanding Real-World Differential Performance Bugs in Machine Learning Libraries](https://mlsanity.com/paper/2006.01991/) (2020)
- [SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities](https://mlsanity.com/paper/1708.08437/) (2017)
- [Differential Performance Debugging with Discriminant Regression Trees](https://mlsanity.com/paper/1711.04076/) (2017)
- [QFuzz: Quantitative Fuzzing for Side Channels](https://mlsanity.com/paper/2106.03346/) (2021)
- [Discriminating Traces with Time](https://mlsanity.com/paper/1702.07103/) (2017)

## Built on by (most cited first, 1 of 1)

- [Fairness Testing through Extreme Value Theory](https://mlsanity.com/paper/2501.11597/) (2025)

## Abstract (arXiv)

This paper leverages the statistics of extreme values to predict the worst-case convergence times of machine learning algorithms. Timing is a critical non-functional property of ML systems, and providing the worst-case converge times is essential to guarantee the availability of ML and its services. However, timing properties such as worst-case convergence times (WCCT) are difficult to verify since (1) they are not encoded in the syntax or semantics of underlying programming languages of AI, (2) their evaluations depend on both algorithmic implementations and underlying systems, and (3) their measurements involve uncertainty and noise. Therefore, prevalent formal methods and statistical models fail to provide rich information on the amounts and likelihood of WCCT. Our key observation is that the timing information we seek represents the extreme tail of execution times. Therefore, extreme value theory (EVT), a statistical discipline that focuses on understanding and predicting the distribution of extreme values in the tail of outcomes, provides an ideal framework to model and analyze WCCT in the training and inference phases of ML paradigm. Building upon the mathematical tools from EVT, we propose a practical framework to predict the worst-case timing properties of ML. Over a set of linear ML training algorithms, we show that EVT achieves a better accuracy for predicting WCCTs than relevant statistical methods such as the Bayesian factor. On the set of larger machine learning training algorithms and deep neural network inference, we show the feasibility and usefulness of EVT models to accurately predict WCCTs, their expected return periods, and their likelihood.