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.