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

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

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.