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

III: Small: A primal-dual framework for data-mining applications

III：小型：数据挖掘应用程序的原始对偶框架

基本信息

批准号：
1908510
负责人：
Alina Ene
金额：
$ 50万
依托单位：
Trustees of Boston University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-09-01 至 2024-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908510&HistoricalAwards=false
关键词：
III Small primal dual framework

项目摘要

The proliferation of mobile devices and social networks has enabled the collection of a wide-range of information related to users' activities. The collected information can be represented as a network capturing the inter-connections between users and the nodes in the network are enriched with extra information resulting from users' activities. Examples of such networks include activity and landmark road networks where the nodes are intersections and the edges are road segments. Every node in an activity network is associated with some type of activity such as geotagged tweets or photos uploaded from the node's vicinity. In landmark networks, nodes are associated with points of interests such as museums, restaurants, and landmarks. A fundamental task arising in the analysis of such networks is to find a set of connected nodes that are close-by in the network and are also associated with high levels of activity. For example, such an analysis can be used to identify the interests of neighborhoods as well as interesting facts about population dynamics. Analogous problems arise in social and collaboration networks, expertise management systems, and team formation. The networks are often massive and thus solving these optimization tasks requires algorithms that are very efficient and allow for a richer and more informative analysis of the data.The project models the optimization problems arising in the aforementioned applications as prize-collecting network design problems: given a graph with connection costs associated with the edges and prizes associated with the nodes, the goal is to find a connected subgraph that has small connection cost as well as high prize. To allow for a richer analysis, the project considers more complex set prize functions that incorporate interactions between nodes and different ways of combining the connection cost and the prize in the objective. The approach is to design algorithms for each class of problems using a template primal-dual framework motivated by the classical algorithm for the prize-collecting Steiner tree problem. Different instantiations of the set prizes require the re-design of specific components of this template algorithm and thus lead to new algorithmic research directions. An important goal is to exploit the structure of the prize functions arising in applications in order to obtain algorithms are very efficient and scalable, in addition to achieving provable approximation guarantees.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.

移动设备和社交网络的普及使得收集与用户活动相关的广泛信息成为可能。收集到的信息可以表示为捕获用户之间相互连接的网络，并且网络中的节点丰富了用户活动产生的额外信息。这种网络的例子包括活动和地标道路网络，其中节点是十字路口，边缘是道路段。活动网络中的每个节点都与某种类型的活动相关联，例如地理标记的tweet或从节点附近上传的照片。在地标网络中，节点与博物馆、餐馆和地标等兴趣点相关联。在分析这种网络时出现的一个基本任务是找到一组连接的节点，这些节点在网络中离我们很近，并且与高水平的活动有关。例如，这样的分析可以用来确定社区的利益，以及关于人口动态的有趣事实。类似的问题出现在社会和协作网络、专业知识管理系统和团队形成中。网络通常是庞大的，因此解决这些优化任务需要非常高效的算法，并允许对数据进行更丰富、更有信息的分析。该项目将上述应用中出现的优化问题建模为奖励网络设计问题：给定一个图，连接成本与边相关，奖励与节点相关，目标是找到一个连接成本小、奖励高的连通子图。为了进行更丰富的分析，该项目考虑了更复杂的集合奖励函数，这些函数包含节点之间的交互以及将连接成本和目标中的奖励结合起来的不同方式。该方法是利用一个模板原对偶框架来设计每一类问题的算法，该框架是由经典的收集奖斯坦纳树问题算法所激发的。集合奖的不同实例需要重新设计该模板算法的特定组件，从而导致新的算法研究方向。一个重要的目标是利用应用程序中出现的奖励函数的结构，以获得非常高效和可扩展的算法，以及实现可证明的近似保证。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（24）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Online Ad Allocation with Predictions

带预测的在线广告分配

DOI：
发表时间：
2023
期刊：
Advances in neural information processing systems
影响因子：
0
作者：
Spaeh, Fabian;Ene, Alina
通讯作者：
Ene, Alina

On the Convergence of AdaGrad(Norm) on R^d: Beyond Convexity, Non-Asymptotic Rate and Acceleration

论 AdaGrad(Norm) 在 R^d 上的收敛性：超越凸性、非渐近率和加速度

DOI：
发表时间：
2023
期刊：
International Conference on Learning Representations
影响因子：
0
作者：
Liu, Zijian;Nguyen, Ta Duy;Ene, Alina;Nguyen, Huy
通讯作者：
Nguyen, Huy

On the Generalization Error of Stochastic Mirror Descent for Quadratically-Bounded Losses: an Improved Analysis

DOI：
发表时间：
2023
期刊：
影响因子：
0
作者：
Ta Duy Nguyen;Alina Ene;Huy Nguyen
通讯作者：
Ta Duy Nguyen;Alina Ene;Huy Nguyen

Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities

约束凸优化和变分不等式的自适应梯度法

DOI：
发表时间：
2021
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
0
作者：
Ene, Alina;Nguyen, Huy L;Vladu, Adrian
通讯作者：
Vladu, Adrian

Characterizing Covid Waves via Spatio-Temporal Decomposition

DOI：
10.1145/3534678.3539136
发表时间：
2022-08
期刊：
Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
影响因子：
0
作者：
K.L. Quinn;Evimaria Terzi;M. Crovella
通讯作者：
K.L. Quinn;Evimaria Terzi;M. Crovella