Worst-Case Convergence Time of ML Algorithms via Extreme Value Theory
Saeid Tizpaz-Niari Sriram Sankaranarayanan
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.