权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

CRII：AF：耐噪声功能测试算法及其在深度学习中的应用

基本信息

批准号：
1657477
负责人：
Grigory Yaroslavtsev
金额：
$ 17.46万
依托单位：
Indiana University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-03-01 至 2021-02-28
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1657477&HistoricalAwards=false
关键词：
CRII AF Algorithms Noise Tolerant

项目摘要

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.

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

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack

DOI：
发表时间：
2019-10
期刊：
ArXiv
影响因子：
0
作者：
Dmitrii Avdiukhin;G. Yaroslavtsev;Samson Zhou
通讯作者：
Dmitrii Avdiukhin;G. Yaroslavtsev;Samson Zhou

Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent

DOI：
10.14778/3324301.3324307
发表时间：
2019-02
期刊：
ArXiv
影响因子：
0
作者：
Dmitrii Avdiukhin;S. Pupyrev;G. Yaroslavtsev
通讯作者：
Dmitrii Avdiukhin;S. Pupyrev;G. Yaroslavtsev

Adversarially Robust Submodular Maximization under Knapsack Constraints

DOI：
10.1145/3292500.3330911
发表时间：
2019-05
期刊：
Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
影响因子：
0
作者：
Dmitrii Avdiukhin;Slobodan Mitrovic;G. Yaroslavtsev;Samson Zhou
通讯作者：
Dmitrii Avdiukhin;Slobodan Mitrovic;G. Yaroslavtsev;Samson Zhou

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under ℓp-Distances

∄p 距离下单连锁聚类的大规模并行算法和硬度