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

EAGER: Developing a Theory for Function Optimization on Graphs Using Local Information

EAGER：开发使用局部信息的图函数优化理论

基本信息

批准号：
1841190
负责人：
Robert Nowak
金额：
$ 17.53万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2021-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1841190&HistoricalAwards=false
关键词：
EAGER Developing Theory Function Optimization

项目摘要

This project seeks to advance the frontiers of knowledge concerning efficient search on networked data. The investigators will devise new algorithms for optimizing a function defined over a graph. Such algorithms will be easily implementable, broadly applicable, and backed by mathematical theory. Some example application areas in which the work will be relevant include faster web retrieval and cybersecurity, where it is important to identify key individuals in a large web of interconnected data. The project will also support the educational goals of the investigators by training multiple graduate students working at the interface of theoretical and applied data science research.The work conducted in this project will establish new connections between continuous and discrete optimization. The investigators will explore notions of smoothness and convexity that may be used to characterize the convergence properties of their proposed optimization algorithms; unlike optimization on graphs, optimization on continuous domains is backed by a mature theory that has been developed over several decades. Developing an analogous theory for discrete domains such as graphs poses many challenges, however -- in particular, it requires developing new notions of derivatives, Hessians, smoothness, or convexity, which have no obvious analogs. This work is divided into the following sub-projects, each with a distinct set of research objectives: (1) Develop and analyze iterative and local algorithms on graphs; (2) Find suitable notions of smoothness and convexity on graphs, and analyze their consequences. In addition, the algorithms will be implemented and evaluated on various real-world networks.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目旨在推进有关有效搜索网络数据的知识前沿。研究人员将设计新的算法来优化定义在图上的函数。这种算法将易于实现，广泛适用，并得到数学理论的支持。这项工作将涉及的一些应用领域包括更快的网络检索和网络安全，在这些领域中，重要的是要在一个庞大的互联数据网络中识别关键个人。该项目还将通过培训多名从事理论和应用数据科学研究的研究生来支持研究人员的教育目标。该项目中进行的工作将在连续优化和离散优化之间建立新的联系。研究人员将探索光滑性和凸性的概念，这些概念可用于表征他们提出的优化算法的收敛特性;与图上的优化不同，连续域上的优化得到了几十年来发展起来的成熟理论的支持。发展一个类似的理论，如图离散域提出了许多挑战，但是-特别是，它需要开发新的概念的衍生物，海森，光滑，或凸性，没有明显的类似物。这项工作分为以下子项目，每个子项目都有一套独特的研究目标：（1）开发和分析图上的迭代和局部算法;（2）找到合适的光滑性和凸性概念，并分析其后果。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Graph-Based Ascent Algorithms for Function Maximization

DOI：
10.1109/allerton.2018.8636074
发表时间：
2018-02
期刊：
2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
影响因子：
0
作者：
Muni Sreenivas Pydi;Varun Jog;Po-Ling Loh
通讯作者：
Muni Sreenivas Pydi;Varun Jog;Po-Ling Loh

Teaching and Learning in Uncertainty

不确定性中的教与学