Approximations of computationally intensive statistical learning algorithms: theory and methods

点击翻译按钮获取中文摘要

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.