CAREER: Faster and Smaller Sketches for Bigger Data

职业：更快、更小的草图以获取更大的数据

• 批准号: 1750716
• 负责人: Huy Nguyen
• 金额: $ 49.99万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-01 至 2024-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750716&HistoricalAwards=false
• 关键词: CAREER; Faster; Smaller; Sketches; Bigger

The advent of new sensing and tracking technologies and expansive use of social networks detailing every walk of life have generated enormous new datasets. The difficulty in dealing with new datasets arises from not only the sheer volume but also the speed required for the analysis and the complex and heterogeneous nature of the data. Underlying these challenges is the need for suitable representations of the data that facilitate efficient computation and are sufficiently compact for storage and communication. This project aims to address fundamental gaps in our understanding of these representations (so-called sketches) and develops both new data representations and new algorithms for massive datasets in a holistic fashion. The project builds on techniques from a wide variety of areas including mathematical analysis, information theory, coding theory, combinatorics, and optimization, and enriches the deep connections among them. Undergraduate and graduate students will be trained and equipped with technical tools to work in these areas. The PI and the students involved in the project will also distill new findings into general audience surveys and give talks at workshops in different technical areas for broadest possible dissemination of information.This project aims to study sketching algorithms by focusing on three main thrusts:(a) Study time complexity of sketches in streaming algorithms in both upper and lower bounds.(b) Develop new forms of sketches for distributed environments. The project focuses on sketching for submodular functions, a popular model for machine learning, computer vision, economics, etc. Problems in these applications are modeled as submodular maximization subject to various types of constraints. (c) Study space complexity of linear sketches in sparse recovery with respect to different recovery guarantees.

新的传感和跟踪技术的出现以及详细描述各行各业的社交网络的广泛使用产生了大量新的数据集。处理新数据集的困难不仅来自数量庞大，而且来自分析所需的速度以及数据的复杂性和异质性。这些挑战的基础是需要适当的数据表示，以促进有效的计算，并足够紧凑的存储和通信。该项目旨在解决我们对这些表示（所谓的草图）的理解中的根本差距，并以整体的方式为大规模数据集开发新的数据表示和新的算法。该项目建立在各种领域的技术基础上，包括数学分析，信息论，编码理论，组合数学和优化，并丰富了它们之间的深层联系。本科生和研究生将接受培训，并配备在这些领域工作的技术工具。参与计划的主要研究者及学生亦会将新的研究结果归纳为一般观众调查，并在不同技术范畴的工作坊上发表演讲，以尽量广泛地传播信息。本计划旨在研究素描算法，主要集中于三个方面：（a）研究流算法中素描的时间复杂度的上限及下限。(b)为分布式环境开发新形式的草图。该项目的重点是子模块化功能的草图，这是机器学习，计算机视觉，经济学等的流行模型，这些应用中的问题被建模为子模块化最大化受到各种类型的约束。(c)研究了线性草图稀疏恢复在不同恢复保证下的空间复杂度。

项目成果

Improved Frequency Estimation Algorithms with and without Predictions

• DOI: 10.48550/arxiv.2312.07535
• 发表时间: 2023-12
• 期刊: ArXiv
• 作者: Anders Aamand;Justin Y. Chen;Huy Le Nguyen;Sandeep Silwal;A. Vakilian

Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities

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

• 发表时间: 2021
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Ene, Alina;Nguyen, Huy L;Vladu, Adrian
• 通讯作者: Vladu, Adrian

Differentially Private Decomposable Submodular Maximization

• DOI: 10.1609/aaai.v35i8.16860
• 发表时间: 2020-05
• 期刊: ArXiv
• 作者: Anamay Chaturvedi;Huy L. Nguyen;Lydia Zakynthinou

Differentially Private Clustering via Maximum Coverage

• DOI: 10.1609/aaai.v35i13.17375
• 发表时间: 2020-08
• 作者: Matthew D. Jones;Huy L. Nguyen;Thy Nguyen

Fast greedy for linear matroids

快速贪婪线性拟阵

• DOI: 10.1137/1.9781611975482.32
• 发表时间: 2019
• 期刊: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Nguyen, H.