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.