A Non-Asymptotic Analysis of Stochastic Mirror Descent for Non-Convex Learning

许多最先进的机器学习技术在很大程度上依赖于一些非凸目标的优化。通常，这个过程在计算上是昂贵的，并且需要使用随机近似或使用人工噪声的正则化技术。例如，深度学习中有各种各样的技术，它们将人工噪声应用于数据、参数或更新方向，所有这些都被证明可以促进更快的收敛和改进的泛化。虽然这些技术中的许多已经通过反复的实验和测试证明了它们的有效性，但验证和理解它们的理论框架仍处于起步阶段。另一种用于克服上述计算困难的技术是镜像下降框架，它通过利用已知的特定于所考虑问题的几何特性来实现。它在凸优化中非常流行，因为在这种情况下，该算法有许多可证明的优点。它的随机对应，随机镜像下降，在非凸学习中迅速流行起来。但同样，这方面的理论框架还不完善。通过我们的项目，我们试图更好地理解这些技术在大规模学习环境中的统计和计算特性。具体来说，我们感兴趣的是定量比较这些技术的一致性和泛化性能，并观察它们如何随着问题变得更具挑战性而变化。指导我们的方法学将主要关注非渐近分析，这与量被取到无限极限的分析相比较。我们相信这对于大规模学习的应用程序是必不可少的，因为只有有限的迭代可以发生，并且参数数量对性能的影响是关键。从根本上说，我们的方法将基于用随时间不断进化的随机过程（特别是扩散过程）逼近迭代优化过程。有了这个，我们获得了分析扩散的一整套强大的技术。这种方法近年来越来越受欢迎，并且已经在学习环境中产生了有趣的结果。该项目还将大量借鉴随机微分方程和高维统计的研究。该项目属于EPSRC统计和应用概率领域。

Many state of the art machine learning techniques depend heavily on the optimisation of some non-convex objective. Often, this procedure is computationally expensive and requires techniques that employ stochastic approximations or regularisation using artificial noise. For instance, there are a variety of techniques in deep learning that use artificial noise applied to the data, parameters or update direction, all of which have been shown to encourage faster convergence and improved generalisation. Though many of these techniques have demonstrated their validity through repeated experimentation and testing, the theoretical framework to validate and understand them is still in its infancy.Another technique which is used to overcome the aforementioned computational difficulties is the mirror descent framework, which does so by taking advantage of the known geometric properties specific to the problem in consideration. It is highly popular in convex optimisation as in this setting there are many provable advantages to this algorithm. Its stochastic counterpart, stochastic mirror descent, is rapidly gaining popularity in non-convex learning. But again, the theoretical framework in this setting is under-developed.Through our project, we seek to develop a better understanding of the statistical and computational properties of these techniques in the large-scale learning setting. Specifically, we are interested in quantitively comparing the consistency and generalisation performance of these techniques and seeing how they change as the problem grows more challenging.Guiding much of our methodology will be the focus on non-asymptotic analysis, that is compared to analyses in which quantities are taken to their infinite limits. We believe this is essential for applications in large-scale learning where only a limited number of iterations can take place and the effect of the number of parameters on performance is of key interest.Fundamentally, our approach will be based on approximating the iterative optimisation procedure with stochastic processes that evolve continuously in time, specifically diffusion processes. With this, we gain access to the broad suite of powerful techniques for analysing diffusions. This approach has seen a growing popularity in recent years and has already yielded interesting results in the learning setting. The project will also draw heavily from the study of stochastic differential equations as well as high dimensional statistics.This project falls within the EPSRC Statistics and Applied probability area.