Reference number : GC-2017-Q1-01489, amendment number : , agreement type : G, recipient legal name : Devroye, Luc (McGill University)|Devroye, Luc (Université McGill), recipient country : CA, recipient province : nan, recipient city : Quebec|Québec, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : We seek to further the understanding of probabilistic phenomena that occur in the design and behavior of algorithms, data structures, networks, graphs and pattern recognition (machine learning) methods. The long-term plan has four axes of research: 
 
(1) The in-depth analysis of random trees and random structures that are practically relevant. We will in particular focus on families of randomized trees that act on arbitrary non-random high-dimensional data, on random tries (in the context of the bit model of complexity), and on hyperplane search trees. 
 
(2) Networks with geometric, connectivity, directional, or other restrictions appear in many contexts. We propose to study broad classes of them and pay particular attention to connectivity thresholds, emergence of giant components, diameter, and structural properties in general. Included are Kademlia and peer-to-peer networks, random Erdos-Renyi graphs with external high-dimensional parameters, and various brands of random geometric graphs. 
 
(3) The continued effort to design universally consistent but also computationally efficient classifiers, with particular attention given to tree classifiers. Random forest classifiers are of special interest in view of their simplicity. As part of this effort, we will try to understand, theoretically, why deep learning networks are often successful, and investigate the relationship between the accuracy of these learning networks and their complexity beyond classical measures such as the Vapnik- Chervonenkis dimension. 
 
(4) The development of new paradigms for random variate generation and the exact simulation of objects or processes that hitherto could either not be generated in an exact manner, or could at best be generated inefficiently. In addition, we will develop Shannon style information-theoretic lower bounds, and hopefully matching upper bounds, for the expected number of random fair bits needed to generate random variables with a desired accuracy., program purpose french : We seek to further the understanding of probabilistic phenomena that occur in the design and behavior of algorithms, data structures, networks, graphs and pattern recognition (machine learning) methods. The long-term plan has four axes of research: 
 
(1) The in-depth analysis of random trees and random structures that are practically relevant. We will in particular focus on families of randomized trees that act on arbitrary non-random high-dimensional data, on random tries (in the context of the bit model of complexity), and on hyperplane search trees. 
 
(2) Networks with geometric, connectivity, directional, or other restrictions appear in many contexts. We propose to study broad classes of them and pay particular attention to connectivity thresholds, emergence of giant components, diameter, and structural properties in general. Included are Kademlia and peer-to-peer networks, random Erdos-Renyi graphs with external high-dimensional parameters, and various brands of random geometric graphs. 
 
(3) The continued effort to design universally consistent but also computationally efficient classifiers, with particular attention given to tree classifiers. Random forest classifiers are of special interest in view of their simplicity. As part of this effort, we will try to understand, theoretically, why deep learning networks are often successful, and investigate the relationship between the accuracy of these learning networks and their complexity beyond classical measures such as the Vapnik- Chervonenkis dimension. 
 
(4) The development of new paradigms for random variate generation and the exact simulation of objects or processes that hitherto could either not be generated in an exact manner, or could at best be generated inefficiently. In addition, we will develop Shannon style information-theoretic lower bounds, and hopefully matching upper bounds, for the expected number of random fair bits needed to generate random variables with a desired accuracy., agreement title english : Probabilistic methods in computer science and machine learning, agreement title french : Probabilistic methods in computer science and machine learning, agreement number : RGPIN, agreement value : 355000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada