Approximations of computationally intensive statistical learning algorithms: theory and methods

定量科学的从业者（统计学家、工程师、物理学家等）经常面临棘手的数量，例如计算一个不能解析解的积分或优化一个不明确已知的函数。在这两种情况下，感兴趣的数量都被称为难以处理的，因为它的精确（数学）值是无法达到的。这种情况通常使用随机数值算法来解决：这是一种迭代方法，使用在计算机上实现的随机数序列，返回数值给用户，近似于他们棘手问题的精确解。基于这个数值输出，从业者可以对数据进行分类，评估模型，解释实验等。因此，必须很好地理解算法的收敛性，并且它应该返回一个概率准确的值。自20世纪50年代以来，统计学和机器学习领域的大量研究都致力于设计具有坚实理论基础的算法。这类算法包括马尔可夫链蒙特卡罗方法、期望最大化算法、梯度算法等。这些被称为标准算法，因为它们被大多数应用科学家所熟知和使用：在常规情况下，算法被视为一个黑盒，只要迭代足够的时间，它就会收敛并返回一个值得信赖的问题解决方案。

Practitioners of quantitative sciences (statisticians, engineers, physicists, etc.) often face intractable quantities, such as calculating an integral which cannot be solved analytically or optimizing a function which is not known explicitly. In both cases, the quantity of interest is referred to as intractable since its exact (mathematical) value is out of reach. Such a situation is usually solved using stochastic numerical algorithms: those are iterative methods using sequences of random numbers implemented on a computer which return a numerical value to the user, approximating the exact solution to their intractable problem. Based on this numerical output, the practitioner can classify data, assess a model, interpret an experiment, etc. The algorithm convergence must thus be well understood and it should return a value which is probabilistically accurate. Since the 1950s, a lot of research in statistics and machine learning has been devoted to designing algorithms that have a solid theoretical foundation. Such algorithms include Markov chain Monte Carlo methods, Expected Maximization algorithm, the gradient algorithm, etc. Those are referred to as standard algorithms as they are known and used by most applied scientists: in regular situations, the algorithm, seen as a black-box, converges and returns a trustworthy solution to the problem as long as it iterates a sufficient amount of time. Paradoxically, the increasing computational capacity of today's computers challenges the efficiency of standard algorithms. We outline two situations where they scale poorly to the dimension of the problem. - big data: improved storage capacity and better data-acquisition devices mean that algorithms can be supplied with more data (and more accurate ones). Standard algorithms become computationally slow and in fact unusable in practice. - high-dimensionality: novel computer architectures (parallel computing, GPU, etc.) allow scientists to attempt solving more complex problems such as integrating functions of several hundred variables. Standard algorithms become statistically slow, i.e. they need much more iterations for achieving a given accuracy than for lower dimensional problems. The main research line of this proposal deals with the approximation of some standard algorithms. Expected outputs include statistical methods that are computationally and statistically more efficient than standard algorithms while still retaining, in some capacity, their black-box aspect. Designing an approximation framework that guarantees that most theoretical properties of the standard algorithm are preserved in the noisy version is essential. Promising results have already been obtained for some algorithms and have been successfully applied to social network analysis and computer vision. Current research aims at making those approximate methods more generic and unifying the theoretical frameworks for analyzing and designing new approximate algorithms.