Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McGill University

$29,000.00

Concentrated Optimization for Machine Learning: Complexity in High-Dimensions, Average-case Analysis, and Exact Dynamics

EF 2024-25

Résumé
Learning algorithms play an integral role in machine learning and have had widespread empirical success in training high-dimensional problems (e.g., number of features and samples are large). In spite of their popularity, there is a gap between real-world performances and best known theoretical bounds. Traditionally, complexity theory of learning algorithms focuses on worst-case analysis, which guarantees convergence for all inputs under general assumptions of the objective function such as convexity and smoothness. High-dimensionality is often not explicitly assumed. High-dimensional data implies more possibilities for the inputs into an algorithm so the input which generate the worst-case complexity could be far from typical. Average-case analysis places a probability distribution on the inputs and computes the expected complexity. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. A challenge is finding a good probability distribution on the input (data set) that matches real-world successes and is amenable to analysis. This proposal addresses a series of research questions relating average-case complexity of first-order methods and high-dimensionality. The proposal seeks to answer the following question. Develop a general framework for average-case complexity of learning algorithms and analyze their exact dynamics to gain insights into step size selections and convergence properties. The proposal has two components. First, the PI explores questions concerning high-dimensional dynamics of stochastic optimization algorithms on a random least squares problem. In particular, the PI plans on investigating the relationships between average-case complexity, step-size and momentum parameter selection strategies, batch-size, and modeling assumptions on the data-set and targets. Indeed lots of computational time is wasted trying to find step-sizes which (1). yield good optimizers and (2). do so in a reasonable amount of time. Average-case analysis can illuminate parameter selections that work for typical high-dimensional problems. Second for various minimization problems (e.g., generalized linear models (GLMs), non-smooth objective functions), one lacks good models for the behavior of real-data as inputs into the objective functions and in particular a model for the Hessian. The spectrum of the Hessian provides a picture of the loss landscape for complicated objective functions. The PI plans on approximating this spectrum with random matrices. Using Hessians generated by random matrices, one can extend the average-case analysis beyond quadratic models to more complicated objective functions.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2022-04034
Name nom
Paquette, Courtney
Department département
Mathematics and Statistics
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
29000
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
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Concentrated Optimization for Machine Learning: Complexity in High-Dimensions, Average-case Analysis, and Exact Dynamics
Keywords
optimization; data science; stochastic algorithms; machine learning; algorithms
Application summary
Learning algorithms play an integral role in machine learning and have had widespread empirical success in training high-dimensional problems (e.g., number of features and samples are large). In spite of their popularity, there is a gap between real-world performances and best known theoretical bounds. Traditionally, complexity theory of learning algorithms focuses on worst-case analysis, which guarantees convergence for all inputs under general assumptions of the objective function such as convexity and smoothness. High-dimensionality is often not explicitly assumed. High-dimensional data implies more possibilities for the inputs into an algorithm so the input which generate the worst-case complexity could be far from typical. Average-case analysis places a probability distribution on the inputs and computes the expected complexity. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. A challenge is finding a good probability distribution on the input (data set) that matches real-world successes and is amenable to analysis. This proposal addresses a series of research questions relating average-case complexity of first-order methods and high-dimensionality. The proposal seeks to answer the following question. Develop a general framework for average-case complexity of learning algorithms and analyze their exact dynamics to gain insights into step size selections and convergence properties. The proposal has two components. First, the PI explores questions concerning high-dimensional dynamics of stochastic optimization algorithms on a random least squares problem. In particular, the PI plans on investigating the relationships between average-case complexity, step-size and momentum parameter selection strategies, batch-size, and modeling assumptions on the data-set and targets. Indeed lots of computational time is wasted trying to find step-sizes which (1). yield good optimizers and (2). do so in a reasonable amount of time. Average-case analysis can illuminate parameter selections that work for typical high-dimensional problems. Second for various minimization problems (e.g., generalized linear models (GLMs), non-smooth objective functions), one lacks good models for the behavior of real-data as inputs into the objective functions and in particular a model for the Hessian. The spectrum of the Hessian provides a picture of the loss landscape for complicated objective functions. The PI plans on approximating this spectrum with random matrices. Using Hessians generated by random matrices, one can extend the average-case analysis beyond quadratic models to more complicated objective functions.