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

点击翻译按钮获取中文摘要

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.