Nonlinear Partial Differential Equations, Monotone Numerical Schemes, and Scaling Limits for Semi-Supervised Learning on Graphs

机器学习旨在利用数据的力量来训练算法做出预测，并在科学、工程、医学和日常生活中执行复杂的任务。尽管机器学习取得了广泛的成功，但典型数据集的不断增长正在带来严重的计算挑战，部分原因是我们对算法在大数据制度下如何工作的理解不完全。这个项目的第一个目标是在机器学习的一个分支-基于图的半监督学习-中解决这些问题，该学习在蛋白质测序、网站分类和语音识别等问题中得到了应用。研究人员分析了最近提出的一些半监督学习算法。对这些算法的深入数学理解解释了它们为什么有效，更重要的是，解释了它们何时会失败。研究人员利用这些见解来开发新的、快速的、更有效的半监督学习算法。本项目的第二个目标是开发和研究稳定、高效和收敛的曲线曲面曲率运动的新算法。曲率运动在科学和工程中有许多应用，包括材料科学、计算机视觉、图像处理以及最近在数据科学和机器学习中的应用。例如，曲率运动描述了肥皂气泡的运动以及多晶材料(如金属和陶瓷)在制造过程中的演变。由于机器学习和曲率运动在科学和工程中都有非常广泛的应用，算法的任何改进和我们对它们的理解都可能产生广泛的社会影响。本项目的第一个目标是严格研究最近提出的基于LP-Laplace正则化的基于图的半监督学习算法。特别地，研究人员证明了学习算法具有对应于求解粘性意义下的加权p-Laplace方程的连续界。在有标签的小数据和无限的无标签数据的限制下，最近的猜想是，当p小于数据的内在维度时，LP-Laplace正则化是不适定的。该项目旨在严格解决这一猜想。研究人员利用这些连续统极限来研究标记数据的分数与算法性能之间的关系，并基于这些见解开发新的更高效的计算算法。该项目的第二个目标是开发和分析一类新的单调有限差分格式，用于曲率驱动的曲线和曲面运动，并对其进行严格的收敛证明。这位研究者最近发现了一种用于构造一大类曲线曲面曲率运动的单调有限差分格式的一般方法。他实现了各种运动的新格式，实验测试了收敛速度，并使用Barles-Souganidis框架严格证明了收敛到粘性解。新格式的单调性允许开发完全隐式和无条件单调的时间推进格式，并确保近似捕捉到正确的连续介质动力学。

Machine learning aims to harness the power of data to train algorithms to make predictions and perform complex tasks in science, engineering, medicine, and everyday life. Despite the wide success of machine learning, the growing size of typical data sets is creating serious computational challenges, partially due to our incomplete understanding of how algorithms work in the big data regime. The first goal of this project is to address these issues within a branch of machine learning called graph-based semi-supervised learning, which has found applications in problems such as protein sequencing, website classification, and speech recognition. The investigator analyzes some recently-proposed algorithms for semi-supervised learning. A deep mathematical understanding of these algorithms explains why they work and, more importantly, when they will fail. The investigator uses these insights to develop new, fast, and more efficient algorithms for semi-supervised learning. The second goal of this project is to develop and study new algorithms for curvature motions of curves and surfaces that are stable, efficient, and convergent. Curvature motion has found many applications in science and engineering, including materials science, computer vision, image processing, and recently in data science and machine learning. Curvature motion describes, for example, the motion of soap bubbles as well as the evolution of polycrystalline materials (such as metals and ceramic) during the manufacturing process. Because both machine learning and curvature motions have very broad applications across science and engineering, any improvement in algorithms and in our understanding of them could have broad societal impacts.The first objective of this project is to study rigorously a recently-proposed algorithm for graph-based semi-supervised learning based on Lp-Laplacian regularization. In particular, the investigator proves that the learning algorithms have continuum limits that correspond to solving a weighted p-Laplace equation in the viscosity sense. In the limit of small labeled data and infinite unlabeled data, it has recently been conjectured that Lp-Laplacian regularization is ill-posed when p is smaller than the intrinsic dimension of the data. The project aims to settle this conjecture rigorously. The investigator uses these continuum limits to study the relationship between the fraction of labeled data and the performance of the algorithms, and to develop new and more efficient computational algorithms based on these insights. The second objective of the project is to develop and analyze a new class of monotone finite difference schemes for curvature-driven motions of curves and surfaces, for which rigorous convergence proofs are available. The investigator has recently discovered a general technique for constructing monotone finite difference schemes for a wide class of curvature motions of curves and surfaces. He implements the new schemes for a variety of motions, experimentally tests convergence rates, and rigorously proves convergence to the viscosity solution using the Barles-Souganidis framework. Monotonicity of the new schemes allows for the development of fully implicit and unconditionally monotone time-stepping schemes, and guarantees the approximations are capturing the correct continuum dynamics.