Grant: Discovery Grants Program - Individual
University of Toronto
$39,000.00
Non-convex Optimization for Machine Learning: Theory and Methods
FY 2019-20
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-06167
Name nom
Erdogdu, Murat
Department département
Computer Science (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2019
Award amount
39000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Installment
NA
Partie
0
Nb partie
NA
Application title
Non-convex Optimization for Machine Learning: Theory and Methods
Keyword
NSERC
Application summary
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.