Non-convex Optimization for Machine Learning: Theory and Methods

机器学习的非凸优化：理论与方法

• 批准号: RGPIN-2019-06167
• 负责人: Erdogdu, Murat
• 金额: $ 2.84万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715953
• 关键词: Non; convex; Optimization; Machine; Learning

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.

非凸优化已经成为人工智能不可缺少的组成部分