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

Indiana University, Bloomington IN

Investigators

Abstract

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.