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.