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

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.

本文利用极值的统计数据来预测机器学习算法的最坏情况。时间安排是ML系统的关键非功能性属性，提供最差的案例收敛时间对于确保ML及其服务的可用性至关重要。但是，很难验证定时属性（例如最差的融合时间（WCCT）），因为（1）它们未在AI的基础编程语言的语法或语法中编码，（2）他们的评估取决于算法实现和基础实现系统，（3）它们的测量涉及不确定性和噪声。因此，普遍的形式方法和统计模型未能提供有关WCCT的数量和可能性的丰富信息。我们的主要观察结果是，我们寻求的时序信息代表了执行时间的极端尾巴。因此，极端价值理论（EVT）是一种统计学科，侧重于理解和预测结果尾部中极值的分布，为在ML范式的训练和推理阶段中建模和分析WCCT提供了理想的框架。在EVT的数学工具的基础上，我们提出了一个实用的框架，以预测ML的最坏情况定时属性。在一系列线性ML训练算法上，我们表明EVT比相关统计方法（例如贝叶斯因素）实现了预测WCCT的精度。在较大的机器学习训练算法和深度神经网络推断上，我们展示了EVT模型准确预测WCCT，其预期返回期以及其可能性的可行性和实用性。