CRII: AF: Algorithms for Noise-Tolerant Function Testing with Applications to Deep Learning

机器学习已经成为计算机科学的一个重要领域，它有可能显著改变我们的生活和社会。在深度学习中，需要依赖于能够快速测试目标函数的性质。这个项目的目标是开发用于测试高维函数的解析性质的算法。更好地理解深度学习中使用的优化目标的性质，将使该领域的研究人员能够就优化方法的选择做出更有教育意义的决策。它将简化并引入参数调整技术中的严谨性，参数调整在实现深层神经网络训练的高性能方面发挥着关键作用。由PI开发的近似算法功能分析(LP-TEST)框架是本研究的起点，已在宾夕法尼亚大学和布宜诺斯艾利斯大学的大数据学习理论和算法课程中讲授。连同这项提案中的研究成果，它将被纳入印第安纳大学由PI教授的数据科学基础和大数据算法的硕士/博士课程。PI将开发超高效算法，帮助人类理解高维函数的分析特性和深度学习中使用的目标。设计这类工具的三个主要目标和相关挑战是：(1)在缺乏明确的全局结构的情况下执行深度学习目标的局部属性的算法分析(2)能够基于噪声数据对函数的分析属性进行严格的分析(3)引入对深度学习应用中出于性能原因而产生的函数评估中的采样误差的容忍度。该项目将涉及开发新的数学方法，以了解随机低维线性空间上的投影如何影响噪声函数的全局性质，如单调性、凸性和Lipschitz性。它将为生成这样的子空间建议分布的选择，以便最好地保持所需的性质。对依赖数据的方法的基本优势的严格研究将作为该项目的单独部分进行。

Machine learning has emerged as an important area of computer science, which has a potential significantly to change our lives and society. In deep learning, one needs to rely on being able to quickly test the properties of objective functions. The goal of this project is to develop algorithms for testing analytic properties of high-dimensional functions. Better understanding of properties of optimization objectives used in deep learning will enable researchers in the field to make more educated decisions regarding the choice of optimization methods. It will simplify and introduce rigor in the art of parameter tuning that plays key role in achieving high performance in training deep neural nets. The framework for approximate algorithmic functional analysis (Lp-testing) developed by the PI that forms the starting point for this research has been taught in courses on learning theory and algorithms for big data at the University of Pennsylvania and University of Buenos Aires. Together with the outcomes of the research in this proposal it will be included into M.S./Ph.D. classes on foundations of data science and algorithms for big data at Indiana University taught by the PI.The PI will develop ultra-efficient algorithms for assisting humans in their understanding of analytic properties of high-dimensional functions and objectives used in deep learning. Three main goals and related challenges in the design of such tools are:(1) Performing algorithmic analysis of local properties of deep learning objectives in the absence of clear global structure (2) Enabling rigorous analysis of analytic properties of functions based on noisy data (3) Introducing tolerance to sampling errors in function evaluations arising in deep learning applications for performance reasons. The project will involve development of new mathematical methods for understanding how global properties of noisy functions such as monotonicity, convexity and Lipschitzness are affected by projections onto random low-dimensional linear subspaces. It will suggest choices of distributions for generation of such subspaces in order to best preserve the desired properties. A rigorous study of fundamental advantages of data-dependent methods will be conducted as a separate part of the project.