FORGING: Fortuitous Geometries and Compressive Learning

统计机器学习在提供算法方面发挥了重要作用，使我们能够从经验数据中得出有效结论。它的成功关键依赖于严格的数学理论。不幸的是，随着现代数据集的维度越来越高，在“维度诅咒”下聚集的新挑战使得许多现有的数据分析方法不充分、有问题或效率低下，并且许多现有的理论变得缺乏信息。减轻维数诅咒是目前研究的热点。然而，许多基本问题仍未得到解决。这个项目的目的是提供以下两个问题的答案：Q1：什么样的数据分布使给定的高维学习问题更容易或更难解决？Q2：在低维子空间上，什么样的学习问题可以近似地压缩解决？我们提出了一个补充的立场，以寻找方法来对抗维数诅咒的各种观察到的有害影响：我们将利用高维概率空间的一些非常普遍的性质来发展一个统一的理论，以及它的算法含义，以揭示一些精确的条件，使我们能够在低维中解决高维问题。这些条件将取决于问题的几何形状。我们将使用我们已经开始发展的问题依赖压缩扭曲的新概念，它将建立在随机预测和经验过程理论之间迄今尚未开发的联系上。预期结果将适用于一系列不同的机器学习和数据挖掘问题，我们在案例研究中验证了这一点。

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.