Non-convex Optimization for Machine Learning: Theory and Methods

由于流行的机器学习模型的结构特性，非凸优化已经成为人工智能中不可缺少的组成部分。*由于它们在众多学习任务中的关键作用和经验上的成功，*它们已经成为最近优化研究的主要焦点。*机器学习模型的许多重要特征，如泛化和快速训练，*都是从这些优化方法继承而来的；*因此，很好地理解这些算法是至关重要的。*为此，我们使用统计学、扩散理论、*和微分几何的适当工具来解释流行的非凸方法的经验成功。*我们进一步提出了在这种体制下设计更高效算法的新范式*其中可伸缩性是一个结构性问题，*我的研究议程的主要目的是提高我们对已经成为机器学习中主要优化工具的*非凸算法的理解。*我们进一步追求几个方向，以建立在我们的理论发现的基础上，为实际问题设计快速高效的*算法。整个研究计划可以分为三个部分，*同时进行：*1-常用非凸优化算法的理论分析，*2-机器学习的高效优化算法的设计，*3-将这些方法应用于实际问题。*例如，在最近的一项工作中，我们建立了非凸优化任务的*离散化扩散的非渐近分析。*我们的结果提供了显式的有限时间收敛到全局极小值的速度(上面的第一项)。*基于此，我们证明了不同的扩散适用于不同类型的凸函数和非凸函数的优化。这使我们能够设计适用于现有文献(上面的第2项)未涵盖的全局最优化凸函数和*非凸函数的扩散。*我们通过证明为*特定目标函数设计的扩散可以获得更好的全局收敛*保证，从而导致特定问题的算法设计(上面的第3项)。*在该建议中，我们重点介绍了机器学习中两种流行的非凸优化方法：基于1-扩散的优化方法和基于2-矩阵分解的优化方法。基于扩散的非凸优化的早期工作主要集中在一种特定的*扩散，称为朗之万动力学。我们的工作考虑了一般的Ito扩散*，它给我们提供了各种好处，包括快速收敛，*广泛的适用性和更好的收敛性质。*我们进一步研究了广泛使用的基于矩阵分解的非凸方法，并建立了它们的理论保证。对于这两个方向，我们都建立在我们的理论基础上，*并为各种机器学习问题设计了高效和可扩展的算法。*这些算法的应用包括推荐系统、图模型推理、神经网络等。

Non-convex optimization has become an indispensable component of artificial intelligence***due to the structural properties of popular machine learning models.***Owing to their key role and empirical success in numerous learning tasks,***they have been a major focus of recent optimization research.***Many important characteristics of machine learning models,***such as generalization and fast-trainability,***are inherited from these optimization methods;***thus, a good understanding of these algorithms are crucial.******To this end, we use appropriate tools from statistics, diffusion theory,***and differential geometry to explain the empirical success of popular non-convex methods.***We further propose new paradigms for designing more efficient algorithms in this regime***where scalability is a structural issue, yet can be resolved by appealing to non-convex methods.******The main purpose of my research agenda is to improve our understanding on***non-convex algorithms which have become the dominant optimization tools in machine learning.***We further pursue several directions to build on our theoretical findings to design fast and efficient***algorithms for practical problems. The overall research plan can be broken into three sections,***to be pursued simultaneously:******1- Theoretical analysis of commonly used non-convex optimization algorithms,***2- Design of efficient optimization algorithms for machine learning,***3- Applying these methods to real problems.******For example in a recent work, we established non-asymptotic analysis of ***discretized diffusions for non-convex optimization tasks.***Our results provide explicit, finite-time convergence rates to global minima (item 1 above).***Based on this, we show that different diffusions are suitable for optimizing different classes of convex***and non-convex functions. This allows us to design diffusions suitable for globally optimizing convex and ***non-convex functions not covered by the existing literature (item 2 above).***We complement these results by showing that diffusions designed for ***a specific objective function can attain better global convergence***guarantees leading to problem-specific algorithm design (item 3 above).******In this proposal, we focus on two popular non-convex methods in machine learning: ***1- diffusion based and 2- matrix factorization based optimization.******Early work on diffusion based non-convex optimization has focused on a specific***diffusion named Langevin dynamics. Our work considers general Ito diffusions***which provide us with various benefits including fast convergence, ***wide applicability, and better convergence properties. ***We further study widely used matrix factorization based non-convex methods, ***and establish their theoretical guarantees. For both of these directions, we build on our theory, ***and design efficient and scalable algorithms for various machine learning problems.***Applications of these algorithms include recommender systems, ***inference in graphical models, neural networks etc.