Non-convex Optimization for Machine Learning: Theory and Methods

非凸优化已成为人工智能不可缺少的组成部分 由于流行的机器学习模型的结构特性。 由于他们在许多学习任务中的关键作用和经验上的成功， 它们一直是最近优化研究的主要焦点。 机器学习模型的许多重要特征， 例如泛化和快速训练性， 是从这些优化方法继承而来的； 因此，很好地理解这些算法是至关重要的。 为此，我们使用了统计学、扩散理论、 和微分几何来解释流行的非凸方法的经验成功。 我们进一步提出了在该机制下设计更有效的算法的新范例 其中可伸缩性是一个结构性问题，但可以通过求助于非凸方法来解决。 我的研究议程的主要目的是提高我们对 非凸算法已经成为机器学习中的主要优化工具。 我们进一步探索了几个方向，以建立在我们的理论发现的基础上，以快速高效地设计 解决实际问题的算法。整个研究计划可以分为三个部分， 同时进行： 1-常用非凸优化算法的理论分析， 2-设计高效的机器学习优化算法， 3-将这些方法应用于实际问题。 例如，在最近的一项工作中，我们建立了非渐近分析 非凸优化问题的离散化扩散。 我们的结果提供了显式的有限时间收敛到全局极小值的速度(上面的第一项)。 在此基础上，我们证明了不同的扩散方式对不同类型的凸集的优化是合适的 和非凸函数。这使我们能够设计适合于全局优化的凸和 现有文献中未涉及的非凸函数(上文第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.