Grant: Discovery Grants Program - Individual
University of Toronto
$64,000.00
Geometric Methods in Data Analysis
EF 2023-24
Résumé
A geometric view of data, based on treating data points as elements of a high dimensional space, has long traditions in computer science and statistics. For example, in machine learning, it is common to represent data as a collection of points, each point corresponding to a particular example, such as a labeled image. The individual features of the data points, e.g. the pixels of the image, give the coordinates of the data point in a coordinate system. Many standard machine learning tasks can then be formulated geometrically. For example, classifying images according to their content can be formulated as finding an appropriate partition of this high dimensional space of images into geometric shapes. For another example, finding similar images corresponds to finding points that are close in an appropriate distance metric. Such formulations allow leveraging mathematical insights from high-dimensional geometry to solve challenging data analysis tasks. Despite the long traditions of a geometric view of data, for many fundamental data analysis tasks we still lack a complete understanding of how the underlying geometry of the task interacts with its statistical and computational hardness. Relatedly, we often do not know algorithms that solve these tasks and adapt optimally to the geometry of the data. The long-term objective of this project is develop a geometric theory of central algorithmic tasks in data analysis. In particular, the theory should predict the statistical and computational complexity of each task, such as the amount of data required to solve it, and the efficiency of an optimal algorithm for it. The theory should also provide principles for the design of simple, and efficient algorithms that optimally adapt to the underlying geometry of the data. The algorithms should also be dynamic, in the sense of being able to adapt to changes in the data or to the problem being solved. The main areas of data analysis that are of interest for the project are private statistical data analysis, high-dimensional search, and experimental design. The short term objectives in each of these areas that will be attacked using geometric tools are: * In private data analysis: design optimal and efficient algorithms for answering counting queries, and for stochastic optimization problems like classification, logistic, and least-squares regression; design competitive algorithms that enable interactive analysis of the data; characterize what tasks can be solved more efficiently when interaction is allowed in distributed models of private data analysis. * In high dimensional search: characterize the metrics for which there exist efficient near neighbour search data structures based on randomized space partitions, as well as data structures in the more general computational models, such as decision trees. * In experimental design: develop efficient algorithms that approximately compute optimal experimental designs under combinatorial constraints.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2021-03206
Name nom
Nikolov, Aleksandar
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2021
Award amount
64000
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
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Theory of computation
Research subject en
Technologie de l'information
Research subject fr
Théorie de calcul
Application title
Geometric Methods in Data Analysis
Keyword
differential privacy; discrepancy theory; high dimensional geometry; nearest neighbour search; private data analysis; private machine learning
Application summary
A geometric view of data, based on treating data points as elements of a high dimensional space, has long traditions in computer science and statistics. For example, in machine learning, it is common to represent data as a collection of points, each point corresponding to a particular example, such as a labeled image. The individual features of the data points, e.g. the pixels of the image, give the coordinates of the data point in a coordinate system. Many standard machine learning tasks can then be formulated geometrically. For example, classifying images according to their content can be formulated as finding an appropriate partition of this high dimensional space of images into geometric shapes. For another example, finding similar images corresponds to finding points that are close in an appropriate distance metric. Such formulations allow leveraging mathematical insights from high-dimensional geometry to solve challenging data analysis tasks. Despite the long traditions of a geometric view of data, for many fundamental data analysis tasks we still lack a complete understanding of how the underlying geometry of the task interacts with its statistical and computational hardness. Relatedly, we often do not know algorithms that solve these tasks and adapt optimally to the geometry of the data. The long-term objective of this project is develop a geometric theory of central algorithmic tasks in data analysis. In particular, the theory should predict the statistical and computational complexity of each task, such as the amount of data required to solve it, and the efficiency of an optimal algorithm for it. The theory should also provide principles for the design of simple, and efficient algorithms that optimally adapt to the underlying geometry of the data. The algorithms should also be dynamic, in the sense of being able to adapt to changes in the data or to the problem being solved. The main areas of data analysis that are of interest for the project are private statistical data analysis, high-dimensional search, and experimental design. The short term objectives in each of these areas that will be attacked using geometric tools are: * In private data analysis: design optimal and efficient algorithms for answering counting queries, and for stochastic optimization problems like classification, logistic, and least-squares regression; design competitive algorithms that enable interactive analysis of the data; characterize what tasks can be solved more efficiently when interaction is allowed in distributed models of private data analysis. * In high dimensional search: characterize the metrics for which there exist efficient near neighbour search data structures based on randomized space partitions, as well as data structures in the more general computational models, such as decision trees. * In experimental design: develop efficient algorithms that approximately compute optimal experimental designs under combinatorial constraints.