Non-convex Optimization for Machine Learning: Theory and Methods

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

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.