Approximations of computationally intensive statistical learning algorithms: theory and methods

数量科学从业者(统计学家、工程师、物理学家等)经常面临难以处理的量，例如计算不能解析求解的积分或优化不明确知道的函数。在这两种情况下，感兴趣的数量都被称为难处理的，因为它的准确(数学)值是遥不可及的。这种情况通常使用随机数值算法来解决：这些是使用在计算机上实现的随机数序列的迭代方法，这些随机数序列将数值返回给用户，近似于他们棘手问题的精确解。基于这个数字输出，实践者可以对数据进行分类、评估模型、解释实验等。因此，必须很好地理解算法的收敛，并且它应该返回一个概率上准确的值。自20世纪50年代以来，统计学和机器学习方面的大量研究致力于设计具有坚实理论基础的算法。这类算法包括马尔科夫链蒙特卡罗方法、期望最大化算法、梯度算法等。这些算法被称为标准算法，因为它们被大多数应用科学家所熟知和使用：在常规情况下，算法被视为黑匣子，只要迭代足够长的时间，它就会收敛并返回问题的可信解决方案。*矛盾的是，当今计算机日益增长的计算能力挑战了标准算法的效率。我们列出了两种情况，它们不能很好地适应问题的规模。*-大数据：更高的存储容量和更好的数据采集设备意味着可以为算法提供更多(也更准确)的数据。标准算法在计算上变得很慢，实际上在实践中无法使用。*-高维：新的计算机体系结构(并行计算、GPU等)允许科学家尝试解决更复杂的问题，如对数百个变量的函数进行积分。标准算法在统计上变得很慢，也就是说，与低维问题相比，它们需要更多的迭代才能达到给定的精度。*本方案的主要研究方向是一些标准算法的逼近。预期产出包括在计算和统计上比标准算法更有效的统计方法，同时仍在一定程度上保留其黑箱方面。设计一个近似框架以确保标准算法的大多数理论属性在噪声版本中得到保留是至关重要的。一些算法已经取得了令人满意的结果，并已成功地应用于社会网络分析和计算机视觉。目前的研究旨在使这些近似方法更加通用，并统一分析和设计新的近似算法的理论框架。

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.**