FORGING: Fortuitous Geometries and Compressive Learning

点击翻译按钮获取中文摘要

Statistical machine learning has been instrumental in providing algorithms that enable us to draw valid conclusions from empirical data. Its successes rely crucially on a rigorous mathematical theory. Unfortunately, as the modern data sets are increasingly high dimensional, new challenges gathered under the term `curse of dimensionality' render many of the existing data analysis methods inadequate, questionable, or inefficient, and much of the existing theory becomes uninformative. Mitigating the curse of dimensionality receives a lot of research attention currently. However, many fundamental questions remain unresolved. The aim of this project is to provide answers to two of these:Q1: What kinds of data distributions make a given high dimensional learning problem easier or harder to be solved?Q2: What kinds of learning problems can be approximately solved compressively, on a low dimensional subspace?We propose a stance complementary to efforts that look for ways to counter the various observed detrimental effects of the dimensionality curse: We shall exploit some very generic properties of high dimensional probability spaces to develop a unified theory, and its algorithmic implications, to unearth some precise conditions that enable us to solve high dimensional problems in low dimensions. These conditions will depend on the geometry of the problem. We will use a new notion of problem-dependent compressive distortion that we have started developing, and which will build on a so far unexploited connection between random projections and empirical process theory. The expected outcome will be applicable across a range of different machine learning and data mining problems, and we validate this in case studies.